#include <iostream>
#include <cassert>
#include <vector>
#include <algorithm>
#include <sstream>
#include <list>
#include <stack>
#include <queue>
using namespace std;

struct ListNode {
     int val;
     ListNode *next;
     ListNode() : val(0), next(nullptr) {}
     ListNode(int x) : val(x), next(nullptr) {}
     ListNode(int x, ListNode *next) : val(x), next(next) {}
};
//打印链表
void displayList(ListNode *p){
    while( p ){
        cout<< p->val ;
        p = p->next;
        if(p) cout<<"->";
    }
    cout<<endl;
}


//解决方案类
class Solution {
public:
    //连接两个链表
    ListNode* connectList(ListNode *a, ListNode * b) {
        if( !a || !b ) return a ? a : b;
        ListNode *p = a;
        while( p->next ) p = p->next;
        p->next = b;
        return a;
    }
    //反转链表
    ListNode *reverseList(ListNode *head){
        ListNode * p1=head, *t , *rt=new ListNode(0);
        while(p1)  t = p1->next , p1->next = rt->next, rt->next = p1, p1 = t;
        return rt->next;
    }
    //递归调用
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode *firstList  = head ,*secondList = head;
        int i =0;
        ListNode *tailPtr = nullptr;
        while(secondList){ //差分成两个链表
            i++; //处理第i个数据
            if(i < k && secondList->next == NULL) return head;
            if(i == k && secondList->next == NULL )return reverseList(head);
            if(i == k ) {
                tailPtr = secondList;
                secondList = secondList->next;
                tailPtr->next = NULL;
                break;
            }
            secondList = secondList->next;
        }
        firstList = reverseList(firstList) ;
        secondList = reverseKGroup(secondList, k);
        return connectList(firstList , secondList);
    }

};

int main(){
    Solution sp;
    ListNode *p = new ListNode(1,new ListNode(2,new ListNode(3,new ListNode(4,new ListNode(5)))));
    ListNode * ans = sp.reverseKGroup(p,3);
    //ListNode * ans = sp.reverseList(p);
    displayList(ans);
    return 0;
}